package DP;

/**
 * https://leetcode-cn.com/problems/burst-balloons/
 */
public class BurstBalloons {

    /**
     * dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j])
     * 实际代码有3个循环要注意
     */
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int i,j,k;
        //扩展的操作
        int[] A = new int[n+2];A[0]=1; A[n+1]=1;
        for(i=0; i<n;i++) A[i+1] = nums[i];
        n+=2;
        int[][] dp=new int[n][n];//n上面已经+2了，这里就不需要了
        for(int len=3; len <= n; len ++){//为什么从3开始，上面+1了，然后，要去掉最开始一个，只能从3开始，要扎中间的气球
            for(i=0; i<=n-len; i++){//这里就开始dp计算，0--len 的这个片段，各种扎法加起来的最大
                //这里是j=i+len-1，是因为 上面 i<= n-len， 加上来正好抵消len
                j = i+len-1;//左边起点已经有了，这里确定右起点的地方，为什么要i+len,而不是直接len-1?因为我们只考虑某一个范围的
                for(k=i+1; k<j; k++ ){//注意k=i+1 因为
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + A[i]*A[k]*A[j]);
                }
            }
        }

        return dp[0][n-1];
    }


    public static void main(String[] args){
        BurstBalloons b= new BurstBalloons();
        int[] a = {3,1,5,8};
        System.out.println(b.maxCoins(a));

    }


}
